/**
 * Copyright (C) 2013 Daniel Gee.
 * See LICENSE.txt for more details.
 */
package com.rl.dungeon.pathing;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Set;

import com.rl.dungeon.Location;

/**
 * Allows for the tracking of distances from one or more goal locations. This is similar to an
 * Influence Map, same idea really. Goal locations are given, and they need not all be connected,
 * then each location within the map has its distance from a goal computed. Then, when a path is
 * needed from anywhere to the nearest goal point, the class simply makes a path by
 * "rolling downhill" from that location until they're at a goal. Creation of a HillMap instance is
 * the (kinda) slow part, but pathfinding is faster than with A* once a particular HillMap has been
 * generated. Note that paths computed with a HillMap simply travel towards any of the goal points,
 * there's no way to specify which goal point you want.
 * 
 * @author Daniel Gee
 */
public class HillMap
{
	/**
	 * A constant for map cells that are blocked off from movement.
	 */
	private static final int Blocked_Elevation = Integer.MAX_VALUE;

	/**
	 * A constant for map cells that are goals.
	 */
	private static final int Goal_Elevation = 0;

	/**
	 * Tracks the "elevation" of different locations. Goal locations have an elevation of 0, and the
	 * value at a location is how many steps it'll take to get to the nearest goal.
	 */
	private final int[][][] elevation;

	/**
	 * The goal locations of this HillMap. It'd be possible to regenerate this by sifting through
	 * the array.
	 */
	private final Set<Location> goals;

	/**
	 * The map used to generate this HillMap, needed for pathfinding later.
	 */
	private final MoveCostMap map;

	/**
	 * The bounds of this HillMap.
	 */
	private final Location mapEdge;

	/**
	 * Constructs a new HillMap. Uses the provided {@link MoveCostMap} to determine what cells are
	 * walkable or not. If any of the <tt>goals</tt> Locations aren't valid Locations according to
	 * the <tt>map</tt>, then an {@link IllegalArgumentException} is thrown.
	 * 
	 * @param map
	 *            determines the blocked locations of the resulting HillMap
	 * @param mapEdge
	 *            the far map edge of the HillMap.
	 * @param goals
	 *            one or more goal locations that the HillMap should have.
	 */
	public HillMap(MoveCostMap map, Location mapEdge, Set<Location> goals)
	{
		// Setup member variables.
		this.elevation = new int[mapEdge.x + 1][mapEdge.y + 1][mapEdge.z + 1];
		for (int[][] ys : this.elevation)
		{
			for (int[] zs : ys)
			{
				Arrays.fill(zs, HillMap.Blocked_Elevation);
			}
		}
		this.map = map;
		this.mapEdge = mapEdge;
		this.goals = Collections.unmodifiableSet(goals);

		// Setup where we're gonna start checking and adjusting
		List<Location> checkLocations = new ArrayList<>();
		for (Location goal : this.goals)
		{
			if (map.isWalkable(goal))
			{
				this.elevation[goal.x][goal.y][goal.z] = HillMap.Goal_Elevation;
				for (Location l : map.getLocationsAccessableFrom(goal))
				{
					if (!checkLocations.contains(l))
					{
						checkLocations.add(l);
					}
				}
			}
			else
			{
				throw new IllegalArgumentException(goal.toString()
						+ " is not valid within the MoveCostMap given.");
			}
		}

		/**
		 * As long as we have places to check, we make sure that none of the neighbors are lower
		 * than the cost to move into this location. Otherwise, we adjust this location down. If the
		 * active location does get adjusted, then all of its neighbors need to be added to the list
		 * of places to check if they're not already on it.
		 */
		while (!checkLocations.isEmpty())
		{
			Location active = checkLocations.remove(0);
			for (Location neighbor : map.getLocationsAccessableFrom(active))
			{
				if (this.elevation[neighbor.x][neighbor.y][neighbor.z] < this.elevation[active.x][active.y][active.z]
						- map.getMoveCostAt(active))
				{
					this.elevation[active.x][active.y][neighbor.z] = this.elevation[neighbor.x][neighbor.y][neighbor.z]
							+ map.getMoveCostAt(active);
					for (Location loc : map.getLocationsAccessableFrom(active))
					{
						if (!checkLocations.contains(loc))
						{
							checkLocations.add(loc);
						}
					}
				}
			}
		}
	}

	/**
	 * Returns the goal locations as an unmodifiable set.
	 * 
	 * @return the goal locations of this hill map
	 */
	public Set<Location> getGoals()
	{
		return this.goals;
	}

	/**
	 * @return the edge of this HillMap.
	 */
	public Location getMapEdge()
	{
		return this.mapEdge;
	}

	/**
	 * Computes a path to the goal location that's nearest to the specfied starting point. Returns
	 * <tt>null</tt> if the specified location is outside the bounds of the map or a blocked
	 * location (as determined by the MoveCostMap used to generate this instance). Paths returned
	 * from this method can vary from one call to the next if there's more than one shortest path.
	 * 
	 * @param start
	 *            the starting point of the path.
	 * @return the path.
	 */
	public List<Location> getPathFrom(Location start)
	{
		if (start.x > this.elevation.length || start.y > this.elevation[0].length)
		{
			return null;
		}
		if (this.elevation[start.x][start.y][start.z] == HillMap.Blocked_Elevation)
		{
			return null;
		}

		List<Location> path = new ArrayList<>();
		path.add(start);

		Location active = start;

		List<Location> temp = new ArrayList<>();

		while (this.elevation[active.x][active.y][active.z] != HillMap.Goal_Elevation)
		{
			temp.clear();
			for (Location loc : this.map.getLocationsAccessableFrom(active))
			{
				if (this.elevation[loc.x][loc.y][loc.z] < this.elevation[active.x][active.y][active.z])
				{
					temp.add(loc);
				}
			}
			if (temp.size() > 1)
			{
				Collections.shuffle(temp);
			}
			active = temp.remove(0);
			path.add(active);
		}

		return path;
	}
}
